package swordRefersOffer.p52;

import javafx.util.Pair;

/**
 * 求两个链表交点
 * @author: trtan
 * @date: 2021-07-21 08:37
 **/
public class IntersectionOfTwoLinkedLists {
    /**
     * 首先求两链表长度，如果存在交点，那么一定会存在两条可能长度不等的分支在交点汇合
     * 那么只需要较长的那个链表先走两链表长度差值，然后再同时出发即可找到交点
     * @param headA
     * @param headB
     * @return swordRefersOffer.p52.ListNode
     * @author trtan
     * @date 2021/7/21 8:44
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len_a = 0, len_b = 0;
        ListNode tmp = headA;
        while (tmp != null) {
            tmp = tmp.next;
            len_a++;
        }
        tmp = headB;
        while (tmp != null) {
            tmp = tmp.next;
            len_b++;
        }
        int d = Math.abs(len_a - len_b);
        if (len_a > len_b) {
            while (d > 0) {
                d--;
                headA = headA.next;
            }
        } else {
            while (d > 0) {
                d--;
                headB = headB.next;
            }
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        if (headA == null || headB == null) {
            return null;
        }
        return headA;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
